n-皇后问题分析
为什么不是每次都在第一个位置放置皇后？
在算法开始时，第一个位置（棋盘的左上角，即位置(0,0)）是可以放置皇后的，因为初始时所有行、列和对角线都是空闲的。但这并不意味着在每次求解时都必须或总是在这个位置放置皇后。回溯算法的目的是探索所有可能的布局，而不仅仅是以一个固定点作为起始。
回溯过程中的撤销操作
在回溯过程中，如果算法在某个位置放置了皇后，但随后发现这个放置导致无法在棋盘上放置更多皇后，它将撤销（回溯）这一步骤。这意味着即使第一个皇后最初被放置在 (0, 0)，这个位置也可能在后续的探索中被改变。
解的唯一性和最优性
在 N 皇后问题中，每个解都是独立且等价的，只要它满足问题的约束条件。这里不存在传统意义上的“最优解”。回溯算法旨在找出所有可能的解，而不是寻找一个单一的最优解。
解的探索和多样性
此算法通过系统地探索棋盘上的每个位置来确保找到所有可能的解。这包括在不同的位置尝试放置皇后，并在遇到冲突时回溯。这种方法保证了即使初始步骤看起来相似，最终的解决方案也可以非常不同。
对角线判断
斜线上采样的多个点的x、y值的差，即说明多个点可通过减法映射到数组中的同一位置，判断斜线上是否出现过一次皇后，即查看 dia[x - y] 是否为空即可。但这样做减法时可能会得到一个负数，是没法直接映射到数组中的，因此主斜线上做判断时统一加上一个常量保证非负，即dia[x - y
- n]。
主斜线上采样的多个点的x、y值的和，即说明多个点可通过加法映射到数组中的同一位置，判断斜线上是否出现过一次皇后，即判断 udia[x + y] 是否为空即可。
对于坐标
(0,0) (0,1) (0,2) (0,3) (0,4)
(1,0) (1,1) (1,2) (1,3) (1,4)
(2,0) (2,1) (2,2) (2,3) (2,4)
(3,0) (3,1) (3,2) (3,3) (3,4)
(4,0) (4,1) (4,2) (4,3) (4,4)
u + i (x+y)
(0) (1) (2) (3) (4)
(1) (2) (3) (4) (5)
(2) (3) (4) (5) (6)
(3) (4) (5) (6) (7)
(4) (5) (6) (7) (8)
每条从右上到左下的对角线 横纵坐标相加的值都是相等的
u-i+n
(5) (4) (3) (2) (1)
(6) (5) (4) (3) (2)
(7) (6) (5) (4) (3)
(8) (7) (6) (5) (4)
(9) (8) (7) (6) (5)
n-u+i
(5) (6) (7) (8) (9)
(4) (5) (6) (7) (8)
(3) (4) (5) (6) (7)
(2) (3) (4) (5) (6)
(1) (2) (3) (4) (5)
每条从左上角到右下角的这些主对角线都等于同一个值
不用在意下标是从多少开始的
也不用管是u-i+n得到的从右上开始第一条 或是n-u+i得到的从左下开始第一条
我只要知道 通过某种计算 能够判断出一条线即可 我只要知道这条线上是否有皇后存在
管他从什么下标开始从哪边开始 只要不是负数即可
//按单元格判断
//从00位置开始 往右逐个单元格判断是否可放置皇后 若到行末则换行
#include<bits/stdc++.h>
using namespace std;
const int N = 10; // 设置棋盘的最大尺寸
int n; // 实际使用的棋盘大小
//对角线数和边数的关系为 2n-1 所以对角线数组要开2n
bool row[N], col[N], dg[N * 2], udg[N * 2]; // 标记数组，分别代表行、列、正对角线、反对角线是否被占用
char g[N][N]; // 存储棋盘的当前状态，'.' 表示空，'Q' 表示皇后
// 深度优先搜索函数
void dfs(int x, int y, int s) {
if (s > n) return; // 如果放置的皇后数量超过 n，则返回
if (y == n) y = 0, x++; // 如果当前列超过棋盘，移动到下一行的开头
if (x == n) {
if (s == n) { // 如果已放置 n 个皇后且遍历完整个棋盘
for (int i = 0; i < n; i++) puts(g[i]); // 打印当前棋盘布局
puts(""); // 打印空行作为不同解之间的分隔
}
return; // 返回上一层递归
}
// 不放置皇后的情况
g[x][y] = '.';
dfs(x, y + 1, s); // 继续探索下一个位置
/*
正对角线 dg[x + y]:
在一个二维坐标系统中，正对角线是那些满足 x + y = 常数 的点的集合。
（y=-x+b -> b=x+y）
在棋盘中，这意味着从左上角到右下角的所有对角线。
在 N 皇后问题中，我们需要检查是否在同一正对角线上已经放置了皇后。
为此，可以使用 x + y 作为索引来标记或检查对角线。
当 !dg[x + y] 为真时，表示当前位置 (x, y) 所在的正对角线上没有其他皇后。
反对角线 udg[x - y + n]:
(y=x+b -> b=x-y)
对于反对角线（从右上角到左下角的对角线），可以使用 x - y 作为一个标识符。
但是，由于 x - y 可能产生负值，我们需要加上一个偏移量（这里是 n），以确保数组索引始终有效。
udg[x - y + n] 表示的是棋盘上的反对角线。
如果 !udg[x - y + n] 为真，这意味着当前位置 (x, y) 所在的反对角线上没有其他皇后。
*/
// 尝试放置皇后
if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]) {
// 如果当前位置可以放置皇后（即该行、列和对角线上都没有其他皇后）
row[x] = col[y] = dg[x + y] = udg[x - y + n] = true; // 更新标记数组
g[x][y] = 'Q'; // 在棋盘上放置皇后
dfs(x, y + 1, s + 1); // 继续探索下一个位置
// 回溯，撤销皇后
g[x][y] = '.';
row[x] = col[y] = dg[x + y] = udg[x - y + n] = false; // 重置标记数组
}
}
int main() {
cin >> n; // 读入棋盘大小
dfs(0, 0, 0); // 从棋盘左上角开始深度优先搜索
return 0;
}
/*
按行判断
其实一行最多只能放一个皇后 所以可以直接按行判断
按行进行深度优先搜索（DFS）:
在这个版本中，dfs 函数的参数 u 表示当前正在处理的行号。
由于每行只能放置一个皇后，因此算法只需遍历每行的每个列位置，而不是之前版本中的每个单元格。
检查列和对角线的冲突:
col[i] 用于检查第 i 列是否已被占用。
dg[u + i] 和 udg[n - u + i] 分别用于检查当前位置所在的正对角线和反对角线是否已被占用。
放置皇后:
如果在第 u 行的第 i 列放置皇后不会导致冲突，算法就在这个位置放置皇后，然后递归调用 dfs(u + 1) 来处理下一行。
回溯和恢复状态:
在递归调用返回后，需要恢复第 u 行第 i 列的状态，以便在同一行的其他位置尝试放置皇后。
打印解决方案:
当 u == n 时，表示所有行都成功放置了皇后，此时打印出当前的棋盘布局作为一个解决方案。
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 10; // 设置棋盘的最大尺寸
int n; // 实际使用的棋盘大小
char g[N][N]; // 存储棋盘的当前状态，'.' 表示空，'Q' 表示皇后
bool col[N], dg[N * 2], udg[N * 2]; // 标记数组，分别代表列、正对角线、反对角线是否被占用
// 深度优先搜索函数
void dfs(int u) {
if (u == n) { // 如果所有行都处理完毕
for (int i = 0; i < n; i++) puts(g[i]); // 打印当前棋盘布局
puts(""); // 打印空行作为不同解之间的分隔
return;
}
//n-u+i或u-i+n都可以 只要能索引到一条对角线即可 不为负即可
for (int i = 0; i < n; i++) { // 遍历当前行的所有列
// 检查当前位置是否冲突
if (!col[i] && !dg[u + i] && !udg[n - u + i]) {
// if (!col[i] && !dg[u + i] && !udg[u - i + n]) {
g[u][i] = 'Q'; // 在棋盘上放置皇后
// 更新标记数组
col[i] = dg[u + i] = udg[n - u + i] = true;
// col[i] = dg[u + i] = udg[u - i + n] = true;
dfs(u + 1); // 处理下一行
// 回溯，恢复状态
col[i] = dg[u + i] = udg[n - u + i] = false;
// col[i] = dg[u + i] = udg[u - i + n] = false;
g[u][i] = '.'; // 清除皇后
}
}
}
int main() {
cin >> n; // 读入棋盘大小
// 初始化棋盘，所有位置均为空
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
g[i][j] = '.';
}
}
dfs(0); // 从第一行开始深度优先搜索
return 0;
}
💬 评论